/*
 * graphalgorithm.h
 *
 *  Created on: May 28, 2012
 *      Author: nogah
 */

#ifndef GRAPH_H
#define GRAPH_H
#include "graph.h"
#endif
#ifndef GRAPH_ALGORITHM_H
#define GRAPH_ALGORITHM_H

#include <queue>
#include <set>
#include <map>

//#define DEBUG 1
//#define VERBOSE 1

#ifdef DEBUG
# define DPRINTF(arg) printf arg
#else
# define DPRINTF(arg)
#endif

#ifdef VERBOSE
# define VPRINTF(arg) printf arg
#else
# define VPRINTF(arg)
#endif

#define NO_CYCLE_FOUND 0
#define ONE_COMPONENT_CYCLE 1
#define TWO_COMPONENT_CYCLE 2
#define REVERSE_CYCLE 3

class GraphAlgorithm {
public:
  std::map<int, Node*> lut;
  std::list<int> seq;
  void setGraph(std::map<int, Node*>& graph) {
    lut = graph;
  }
  void setSequence(std::list<int>& sequence) {
    seq = sequence;
  }
  int findOneComponentCycle(std::list<int>::iterator startNodeIt, int girth);
  int findTwoComponentCycle(std::list<int>::iterator startNodeIt, int girth);
  int findReverseCycle(std::list<int>::iterator startNodeIt, int girth);
  void computePathMultiplicity(Path &p);
  void modifyTwoComponentCycle(Path &p1, Path& p2);
  void modifyReverseCycle(Path &p1, Path& p2);
};



int GraphAlgorithm::findOneComponentCycle(std::list<int>::iterator startNodeIt, int girth) {

  DPRINTF(("Finding cycle from node %d\n", *startNodeIt));

  if (*startNodeIt <= FIRST_NODE) return NO_CYCLE_FOUND;
  Node *startNode = lut[*startNodeIt];
  if (startNode->pos.size() == 1) {
    return NO_CYCLE_FOUND;
  }

  std::list<int>::iterator nodeIt = startNodeIt;

  if (*++nodeIt <= FIRST_NODE) {
    DPRINTF(("Next to end of sequence -> return;\n"));
    return NO_CYCLE_FOUND;
  }
  --nodeIt;

  // 1-component cycle
  std::set<int> visited;
  visited.insert(*startNodeIt);
  for (int i = 1; i <= girth; i++) {
    if (*++nodeIt <= FIRST_NODE) {
      break;
    }
    if (visited.find(*nodeIt) == visited.end()) {
      DPRINTF(("Visit %d\n", *nodeIt));
      visited.insert(*nodeIt);
    }
    else {
      DPRINTF(("Found 1-component cycle\n"));

      while ((*++nodeIt > FIRST_NODE) && (visited.find(*nodeIt) != visited.end()));

      DPRINTF(("Outgoing node is %d\n", *nodeIt));
      // delete the incoming edge of the cycle
      auto prevIt = startNodeIt;
      --prevIt;
      Node *prevStartNode = lut[*prevIt];
      Node *nextNode = startNode;
      prevStartNode->deleteEdge(nextNode);

      if (*nodeIt > FIRST_NODE) {
        // delete the outgoing edge of the cycle
        prevIt = nodeIt;
        --prevIt;
        Node *prevEndNode = lut[*prevIt];
        nextNode = lut[*nodeIt];
        prevEndNode->deleteEdge(nextNode);

        // connect
        prevStartNode->addNext(nextNode);
      }

      auto tmpIt = startNodeIt;
      while (tmpIt != nodeIt) {
        Node *tmpNode = lut[*tmpIt];
        tmpNode->pos.remove(tmpIt);
        ++tmpIt;
      }

      seq.erase(startNodeIt, nodeIt);

      return ONE_COMPONENT_CYCLE;
    }
  }
  return NO_CYCLE_FOUND;
}

int GraphAlgorithm::findTwoComponentCycle(std::list<int>::iterator startNodeIt, int girth) {
  DPRINTF(("Finding two component cycle from %d\n", *startNodeIt));
  if (*startNodeIt <= FIRST_NODE) return NO_CYCLE_FOUND;
  Node *startNode = lut[*startNodeIt];
  if (startNode->pos.size() < 2) {
    return NO_CYCLE_FOUND;
  }
  if (startNode->nexts.size() <= 1) {
    return NO_CYCLE_FOUND;
  }

  std::list<int>::iterator nodeIt = startNodeIt;

  if (*++nodeIt <= FIRST_NODE) {
    DPRINTF(("Next to end of sequence -> return;\n"));
    return NO_CYCLE_FOUND;
  }
  --nodeIt;

  std::set<int> visited;
  visited.insert(*startNodeIt);
  Path p1;
  p1.push_front(*startNodeIt);
  p1.setStartIt(startNodeIt);

  for (int i = 1; i < girth-1; i++) {

    if (*++nodeIt <= FIRST_NODE) {
      break;
    }
    DPRINTF(("Insert node %d to visited\n", *nodeIt));
    visited.insert(*nodeIt);
    p1.push_back(*nodeIt);
  }

  if (*nodeIt <= FIRST_NODE) {
    p1.setEndIt(--nodeIt);
  }
  else p1.setEndIt(nodeIt);

  for (auto posIt = startNode->pos.begin(); posIt != startNode->pos.end(); posIt++) {

    if (*posIt == startNodeIt) continue;
    if (**posIt == DELETED_NODE) continue;

    if (findOneComponentCycle(*posIt, girth)) {
      return ONE_COMPONENT_CYCLE;
    }

    std::list<int>::iterator otherNodeIt = *posIt;
    std::list<int>::iterator tmpNodeIt = startNodeIt;

    if (*++otherNodeIt == *++tmpNodeIt) continue; // 2 nodes have neighbors with same id

    Path p2;
    p2.push_back(**posIt);

    p2.setStartIt(*posIt);

    for (int i = 1; i < girth-1; i++) {
      if (*otherNodeIt <= FIRST_NODE) break;
      DPRINTF(("---Insert node %d to visited\n", *otherNodeIt));
      p2.push_back(*otherNodeIt);
      if (visited.find(*otherNodeIt) != visited.end()) {
        p2.setEndIt(otherNodeIt);

        p1.trimFromEndTo(*otherNodeIt);

        modifyTwoComponentCycle(p1, p2);

        return TWO_COMPONENT_CYCLE;
      }
      ++otherNodeIt;
    }
    DPRINTF(("--\n"));
  }
  return NO_CYCLE_FOUND;
}

int GraphAlgorithm::findReverseCycle(std::list<int>::iterator startNodeIt, int girth) {

  DPRINTF(("Finding REVERSE cycle from %d\n", *startNodeIt));
  if (*startNodeIt <= FIRST_NODE) return NO_CYCLE_FOUND;

  std::list<int>::iterator nodeIt = startNodeIt;

  if (*++nodeIt <= FIRST_NODE) {
    DPRINTF(("Next to end of sequence -> return;\n"));
    return NO_CYCLE_FOUND;
  }
  --nodeIt;

  Node *startNode = lut[*startNodeIt];
  if (startNode->pos.size() < 2) {
    return NO_CYCLE_FOUND;
  }
  if (startNode->nexts.size() <= 1) {
    return NO_CYCLE_FOUND;
  }

  std::set<int> visited;
  visited.insert(*startNodeIt);
  Path p1;
  p1.push_front(*startNodeIt);
  p1.setStartIt(startNodeIt);



  for (int i = 1; i < girth-1; i++) {
    if (*++nodeIt <= FIRST_NODE) {
      return NO_CYCLE_FOUND;
    }
    DPRINTF(("Insert node %d to visited\n", *nodeIt));
    visited.insert(*nodeIt);
    p1.push_back(*nodeIt);

    Node *node = lut[*nodeIt];
    if (node->pos.size() < 2) continue;


    for (auto posIt = node->pos.begin(); posIt != node->pos.end(); posIt++) {
      if (*posIt == nodeIt) continue;

      Path p2;
      p2.push_back(**posIt);
      p2.setStartIt(*posIt);

      auto otherNodeIt = *posIt;
      ++otherNodeIt;
      for (int j = 1; j < girth-i; j++) {
        if (*otherNodeIt <= FIRST_NODE) break;
        DPRINTF(("****Insert node %d to visited\n", *otherNodeIt));
        p2.push_back(*otherNodeIt);
        if (visited.find(*otherNodeIt) != visited.end()) {
          p1.setEndIt(nodeIt);
          p1.trimFromStartTo(*otherNodeIt);

          p2.setEndIt(otherNodeIt);

          modifyReverseCycle(p1, p2);

          return REVERSE_CYCLE;
        }
        ++otherNodeIt;
      }
      DPRINTF(("**\n"));
    }

  }

  return NO_CYCLE_FOUND;
}

void GraphAlgorithm::modifyTwoComponentCycle(Path &p1, Path &p2) {
  computePathMultiplicity(p1);
  computePathMultiplicity(p2);
  Path *keep, *remove;

  if (p1.comparePath(p2) == IS_BETTER) {
    keep = &p1;
    remove = &p2;
  }
  else {
    keep = &p2;
    remove = &p1;
  }

#ifdef DEBUG
  std::cerr << "Keep 2 comp: ";
  keep->print();
  std::cerr << "Remove 2 comp: ";
  remove->print();
#endif

  keep->incPathMultiplicity();

  auto startIt = remove->getStartIt();
  auto endIt = remove->getEndIt();
  auto tmpIt = startIt;

  ++tmpIt;
  DPRINTF(("*****ENDIT*****: %d\n", *endIt));
  while (tmpIt != endIt) {
    DPRINTF(("DELETE %d\n", *tmpIt));
    Node *n = lut[*tmpIt];
    n->pos.remove(tmpIt);
    ++tmpIt;
  }

  tmpIt = startIt;
  ++tmpIt;
  seq.erase(tmpIt, endIt);

  std::list<int> midNodes = keep->getPath();
  midNodes.pop_front();
  midNodes.pop_back();

  tmpIt = startIt;
  ++tmpIt;
  seq.insert(tmpIt, midNodes.begin(), midNodes.end());

  tmpIt = startIt;
  ++tmpIt;
  for (int i = 0; i < midNodes.size(); ++i) {
    Node *n = lut[*tmpIt];
    n->addPos(tmpIt);
    ++tmpIt;
  }
}

void GraphAlgorithm::modifyReverseCycle(Path &p1, Path &p2) {
  computePathMultiplicity(p1);
  computePathMultiplicity(p2);
  Path *keep, *remove;

  if (p1.comparePath(p2) == IS_BETTER) {
    keep = &p1;
    remove = &p2;
  }
  else {
    keep = &p2;
    remove = &p1;
  }

#ifdef DEBUG
  std::cerr << "Keep reverse: ";
  keep->print();
  std::cerr << "Remove reverse: ";
  remove->print();
#endif

  //keep->incPathMultiplicity();

  auto startIt = remove->getStartIt();
  auto endIt = remove->getEndIt();
  auto tmpIt = startIt;


#ifdef DEBUG
  std::cerr << "ok\n";
#endif
  // delete nodes iter from lut
  --tmpIt;
  Node *prevNode = lut[*tmpIt];
  Node *nextNode = lut[*++tmpIt];
#ifdef DEBUG
  std::cerr << "ok2\n";
  std::cerr << *prevNode;
  std::cerr << *nextNode;
#endif
  prevNode->deleteEdge(nextNode);
#ifdef DEBUG
  std::cerr << "*****ENDIT*****: " << *endIt << "\n";
#endif
  //DPRINTF(("*****ENDIT*****: %d\n", *endIt));
  ++endIt;

  while (tmpIt != endIt) {
#ifdef DEBUG
  std::cerr << "DELETE: " << *tmpIt << "\n";
#endif
    //DPRINTF(("DELETE %d\n", *tmpIt));
    Node *n = lut[*tmpIt];
    n->pos.remove(tmpIt);
    ++tmpIt;
  }
#ifdef DEBUG
  std::cerr << "*****STARTIT___1*****: " << *startIt << "\n";
#endif
  tmpIt = startIt;
  --startIt;
  seq.erase(tmpIt, endIt);

  std::list<int> midNodes = keep->getPath();

  // insert _keep path into the old place of _remove
#ifdef DEBUG
  std::cerr << "*****STARTIT___2*****: " << *startIt << "\n";
#endif
  tmpIt = startIt;
  ++tmpIt;
  seq.insert(tmpIt, midNodes.begin(), midNodes.end());

  tmpIt = startIt;
  prevNode = lut[*tmpIt];
  Node *node;
  ++tmpIt;
#ifdef DEBUG
  std::cerr << "*****TEMPIT___2*****: " << *tmpIt << "\n";
#endif
  for (int i = 0; i < midNodes.size(); ++i) {
    node = lut[*tmpIt];
    node->addPos(tmpIt);
    prevNode->addNext(node);
    prevNode = node;
    ++tmpIt;
  }

  // just connect the last added node to the next (existing) one
  node = lut[*tmpIt];
  prevNode->addNext(node);
}


void GraphAlgorithm::computePathMultiplicity(Path &p) {
  std::priority_queue<int> &multiQ = p.getMultiplicityQueue();
  std::list<QueueEdge*> &edges = p.getEdges();
  Node *node;
  auto it = p.getPath().begin();
  node = lut[*it];
  ++it;
  for (; it != p.getPath().end(); ++it) {
    multiQ.push(node->nexts[*it]->multiplicity);
    edges.push_back(new QueueEdge(node, *it));

    node = lut[*it];
  }
  //std::cout << "edges size: " << edges.size() << "\n";
}


#endif













